#pragma once 

#include<iostream>

using namespace std;

template<class K,class V>
struct BSTNode{

  BSTNode(const K& key = K(),const V& value = V())
  :_pleft(nullptr),
  _pright(nullptr),
  _key(key),
  _value(value)
  {}

  BSTNode<K,V> *_pleft;
  BSTNode<K,V> *_pright;
  K _key;
  V _value;
};

////////////////////////////////

template<class K,class V>
class BinarySearchTree{
  typedef BSTNode<K,V> Node;
  public:

  /*
   * 默认成员函数
   */ 


  //--------------------------------
  
  //构造函数
  
  BinarySearchTree()=default;
          /*强制生成默认构造函数*/

  //--------------------------------

  //拷贝构造

  BinarySearchTree(const BinarySearchTree<K,V> &node){
     _proot =  _CopyNode(node._proot);
  }


  //--------------------------------
  
  //赋值重载操作符
  
  BinarySearchTree<K,V>& operator=( BinarySearchTree<K,V> node){
    swap(_proot,node._proot);
    return *this;

  }

  
  //--------------------------------

  //析构函数 - 使用递归方法 后序遍历进行Destory
    
  ~BinarySearchTree(){
    _Destroy(_proot);
  }

  //--------------------------------
  bool Insert(const K& key,const V& value){
    if(_proot == nullptr){//如果root节点为空说明为空树，空树进行第一次插入
      _proot = new Node(key,value);
      return true;//插入成功进行返回
    }

    Node* cur = _proot;
    Node* tmp;

    while(cur!=nullptr){
      tmp = cur;
      if(key>cur->_key){
        tmp = cur;
        cur = cur->_pright;
      }
      else if(key<cur->_key){
        tmp = cur;
        cur = cur->_pleft;
      }
      else{
        //相同 返回false
          return false;
      }
  }
    if(key>tmp->_key){//链接在右边
      cur = new Node(key,value);
      tmp->_pright = cur;
    }
    else{//链接在左边
      cur = new Node(key,value);
      tmp->_pleft = cur;
    }
   return true;
  }
 
  //-----------------------

  void InOrder(){
    /*
     * 自定义类型成员函数若是需要进行递归时
     * 尽量设置一个子函数来方便递归并使用原成员函数进行调用
     * 
     * 在该自定义类型当中，由于传的参数为private私有成员变量
     * 私有成员变量不方便直接进行传参，所以为了方便传参_proot
     * 在private访问限定符的域当中设置一个子函数用来递归
     * 通过原函数去调用这个私有成员函数
     */
   _InOrder(_proot);
   cout<<endl;
  }


  //-----------------------

  bool Find(const K& key){
    Node*pcur = _proot;
    while(pcur){
      if(key>pcur->_key)  pcur = pcur->_pright;
      
      else if(key<pcur->_key) pcur = pcur->_pleft;
      
      else return true;
    }
    return false;
  }



  //-----------------------
  
  bool Erase(const K& key){

    if(nullptr == _proot) return false;
    //找到这个key值
    Node* pcur = _proot;
    Node* parent = _proot;
    while(pcur){
      //进行遍历找到对应的key值
      if(key>pcur->_key){
        parent = pcur;
        pcur = pcur->_pright;
      }
      else if(key<pcur->_key){
        parent = pcur;
        pcur = pcur->_pleft;
      }
      else{
        //已经找到了对应的key值,需要进行删除
         
        
        //左为空的情况
        if(pcur->_pleft == nullptr){
         
          if(pcur == _proot){
              _proot = pcur->_pright;
              delete pcur;
              return true;
          }
          
            if(parent->_pleft == pcur){
            parent->_pleft = pcur->_pright;
          }
          else{
            parent->_pright = pcur->_pright;
          }
          delete pcur;
          return true;
        }

          //右为空的情况
        else if(pcur->_pright == nullptr){

          //判断极端情况(左为空或者右为空的情况下所删节点为根)
          if(pcur == _proot){
              _proot = pcur->_pleft;
              delete pcur;
              return true;
          }

          if(parent->_pleft == pcur){
            parent->_pleft = pcur->_pleft;
          }
          else {
            parent->_pright = pcur->_pleft;
          }
          delete pcur;
          return true;
        }

         //左右都不为空
        else{
           /*
            * 找到左子树的最右子树或右子树的最左子树
            */

            Node*tmp = pcur->_pright; //右子树的最左子树(最小值)
            Node*tmp_parent = pcur;
            while(tmp->_pleft){
              tmp_parent = tmp;
              tmp = tmp->_pleft;    
            }

            /*
             * 找到符合条件的值,进行伪删除法;
             */
            pcur->_key = tmp->_key;
              //说明该子树存在孩子,需要对该子树进行托孤
              //由于所找的数据为该节点右子树的最小值,说明找到的这个最小值不存在左子树,只需要对右子树进行托孤;
              if(tmp_parent->_pleft == tmp){
                tmp_parent->_pleft = tmp->_pright;
                delete tmp;
              }
              else{
                tmp_parent->_pright = tmp->_pright;
                delete tmp;
              }
            return true;
        }

      }
    }
    //未找到key值,pcur指针已经为空,返回false;
    return false;

  }

  
  private:
  /*
   * 私有成员包括成员函数以及成员变量
   */


   Node *_proot = nullptr; 

  //-----------------------

  protected:


  void _InOrder(Node *root){
    if(root == nullptr){
      return;
    }
  
    _InOrder(root->_pleft);
    cout<<root->_key<<" : "<<root->_value<<endl;;
    _InOrder(root->_pright);
  }
  //-----------------------

    Node* _CopyNode(const Node* node){
      
      if(node == nullptr) {
        return nullptr;
      }
      Node*newnode = new Node(node->_key,node->_value);
      newnode->_pleft = _CopyNode(node->_pleft);
      newnode->_pright = _CopyNode(node->_pright);
      return newnode;
    }

    //------------------------
    
    void _Destroy(Node*& root){
      if(root == nullptr) return;
      _Destroy(root->_pleft);
      _Destroy(root->_pright);
      delete root;
      root = nullptr;
    }

};

